//给你一个区间列表，请你删除列表中被其他区间所覆盖的区间。 
//
// 只有当 c <= a 且 b <= d 时，我们才认为区间 [a,b) 被区间 [c,d) 覆盖。 
//
// 在完成所有删除操作后，请你返回列表中剩余区间的数目。
//
// 
//
// 示例： 
//
// 
//输入：intervals = [[1,4],[3,6],[2,8]]
//输出：2
//解释：区间 [3,6] 被区间 [2,8] 覆盖，所以它被删除了。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= intervals.length <= 1000 
// 0 <= intervals[i][0] < intervals[i][1] <= 10^5 
// 对于所有的 i != j：intervals[i] != intervals[j] 
// 
// Related Topics 贪心算法 排序 Line Sweep 
// 👍 22 👎 0

package leetcode.editor.cn;

import java.util.Arrays;

//Java：删除被覆盖区间
public class RemoveCoveredIntervals{
    public static void main(String[] args) {
        Solution solution = new RemoveCoveredIntervals().new Solution();
        
    }
    
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int removeCoveredIntervals(int[][] intervals) {
        if ( intervals == null || intervals.length == 0 ){
            return 0;
        }
        //先做好排序，左边升序，左边一致时，右边降序
        Arrays.sort( intervals, (a,b)->{
            if( a[0] == b[0] ){
                return b[1] - a[1];
            }
            else {
                return a[0] - b[0];
            }
        } );
        int count = 0;
        int end,pre_end = 0;
        for ( int[] cur : intervals ){
            end = cur[1];
            if( pre_end < end  ){
                count++;
                pre_end = end;
            }
        }
        return count;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
